package LearnAlgorithm.h_标准数学公式;

/*
同余方程 ax ≡ 1 (mod n), 在gcd(a, n) = 1时有解。
这时称：
	求出的x, 是a的, 对模n的, "乘法逆元"。
对于同余方程 ax ≡ 1(mod n), gcd(a,n) = 1的求解
	就是求解方程 ax + ny = 1, (x, y为整数)
	可用扩展欧几里德算法求出
	原同余方程(ax ≡ 1(mod n), gcd(a,n) = 1)的唯一解(x)就是用扩展欧几里德算法得出的x

ax ≡ 1(mod n), gcd(a, n) = 1

ax % n = 1
gcd(a, n) = 1
a * x0 + n * y = 1
 */

/*
#乘法逆元
乘法逆元(在维基百科中也叫倒数，当然是mod p后的,其实就是倒数不是吗?)：
如果ax = 1 (mod p), 且gcd(a, p) = 1 (即a与p互质)，则称：a关于模p的，乘法逆元，是x。
为什么可以用扩展欧几里得求得逆元?
我们都知道模就是余数，
比如：	12 % 5 = 12 - 5 * 2 = 2,
		18 % 4 = 18 - 4 * 4 = 2。(/是程序运算 中的除)
那么：	ax = 1 (mod p) 即 
		ax % p = 1 
		ax % p = ax - p * 商 = 1 (展开)
				 ax - p * y = 1 (设商 = y)
把y写成+的形式就是 ax + p * y = 1,
为方便理解下面我们把p写成b，即
				 ax + b * y = 1。
就表示	"x是a的，对模b的，乘法逆元"，
		"y是b的，对模a的，乘法逆元"。
然后就可以用扩展欧几里得求了。
知道逆元怎么算之后，那么乘法逆元有什么用呢?

做题时如果结果过大一般都会让你模一个数，确保结果不是很大，而这个数一般是1e9+7 (而且这个数又是个素数)
加减乘与模运算的顺序交换不会影响结果，但是除法不行。
有的题目要求结果mod一个大质数，如果原本的结果中有除法，比如除以a，
(除一个数等于乘它的倒数，虽然这里的逆元不完全是倒数，但可以这么理解，毕竟乘法逆元就是倒数的扩展)。

 */
public class g模的逆元 {
	public static void main(String[] args) {
		try {
			long d = new g模的逆元().inverseElement(13, 5);//13x ≡ 1 (mod 5)；a * x0 + n * y = 1；13 * x0 + 5 * y = 1
			System.out.println("最大公约数：" + d);
			System.out.println("特解之一x：" + ExtGcd.x);
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	public long inverseElement(long a, long n) throws Exception {
		long d = ExtGcd.linearEquation(a, n, 1);
		//变换前ExtGcd.x 看作是 x0
		ExtGcd.x = (ExtGcd.x % n + n) % n;
		//变换后ExtGcd.x 看作是 x
		return d;
	}
	
	public static class ExtGcd {
		static long x;
		static long y;
		public static long gcdEx(long a, long b) {
			if (b == 0) {
				x = 1;
				y = 0;
				return a;
			}
			long res = gcdEx(b, a % b);
			long x1 = x;
			x = y;
			y = x1 - a / b * y;
			return res;
		}
		public static long linearEquation(long a, long b, long m) throws Exception {
			long d = gcdEx(a, b);
			if (m % d != 0) {
				throw new Exception("无解");
			}
			long n = Math.abs(m / d);
			x *= n;
			y *= n;
			return d;
		}
		public static long firstSolution(long a, long b, long m) throws Exception {
			long d = gcdEx(a, b);
			if (m % d != 0) {
				throw new Exception("无解");
			}
			b = b / d;
			x = (x % b + b) % b;
			return x;
		}
	}
}


